This invention relates in general to redundant memory storage systems and in particular to provision of data reliability information in redundant memory storage systems.
In the field of computer memory storage, the loss or corruption of data stored in a single location is a matter of concern. One approach to dealing with this problem is to store the same data in two separate locations so that in the event that a first location is unavailable, or that the data in the first location has been lost or corrupted, the stored data may be read from the second, or mirrored, location. In this way, the originally stored data may be recovered even though one storage location was unable to provide the stored data.
A problem which may arise employing the above solution is that during the course of operation of a computer system there may be occasions during which data is written to only one of the mirrored locations. This may arise where one of the storage locations is unavailable for a write operation for some reason. In this situation, one of the mirrored locations will have more recent data than the other.
Subsequently, when the computer system attempts to read data from the mirrored memory locations, the data stored in the two locations may differ. Moreover, where such a disparity in the data values stored in the mirrored locations exists, it is generally not possible to determine which of the two locations has the most recent and most valid data. The system accessing the data may then run the risk of acquiring and using obsolete data without knowing it.
Accordingly, it is a problem in the art that the use of redundant memory locations may lead to two mirrored memory locations having different data stored in them.
It is a further problem in the art that where mirrored memory locations contain different data, it is generally not possible to determine which of the two memory locations was most recently written to.
The present invention is directed to a system and method which flags write operations to two or more mirrored memory locations with identifying data to indicate a degree of recentness or recency of the write operations to each of the various mirrored memory locations within an overall data storage system. The identifying data may be appended to the data written as part of the write operation and stored in the various mirrored memory locations for subsequent evaluation by a read operation. The identifying data may include sequential numbering data to conveniently and directly indicate a vintage or degree of recency of each data storage entry. Although redundant data storage commonly involves writing to two separate memory locations, a number of memory locations greater than two may be employed and remain within the scope of the present invention.
Herein, the terms xe2x80x9cdata recencyxe2x80x9d or xe2x80x9cdata recentnessxe2x80x9d generally refer to the recency with which data was stored to a memory location, the term xe2x80x9cvintagexe2x80x9d generally refers to a time at which data was stored in a memory location, the term xe2x80x9cuser dataxe2x80x9d generally refers to the data being stored and retrieved from the data storage system as distinguished from information which merely describes a degree of storage recency of such user data, the terms xe2x80x9cranked dataxe2x80x9d or xe2x80x9cranked data packetxe2x80x9d generally refer to user data which has been coupled with information describing storage recency of such user data.
In a preferred embodiment, where new data is to be written to mirrored memory locations, the inventive mechanism first reads the sequence numbers associated with the intended target memory locations for the current write operations. The resulting group of sequence numbers are then preferably compared and the most advanced sequence number (wherein the term xe2x80x9cadvancedxe2x80x9d generally refers to more recently stored data) is preferably selected from the group. The selected sequence number is then modified to reflect a still more recent write operation, specifically, the contemplated write operation involving the xe2x80x9cnew dataxe2x80x9d referred to above. The modified selected sequence number is then preferably appended to the new data and written to all of the mirrored memory locations. If all of the mirrored memory locations are successfully written to, the sequence number at each of the mirrored memory locations may be reset, in order to set the sequence number to a more convenient value, and preferably prevent an overflow condition arising from the sequence number being incremented to a value beyond that which its allocated storage area can properly store.
It will be appreciated that a variety of operations and algorithms may be employed to modify a sequence number to indicate a degree of recency. One approach is to use unique sequence numbers for each set of mirrored memory locations and to increment the sequence number by one or another constant value for each write operation to the mirrored memory locations. Herein, the term xe2x80x9cdata storage recency valuexe2x80x9d generally represents a broader range of possible recency indicators than xe2x80x9csequence number.xe2x80x9d Generally, sequence numbers are but one of many possible forms of data storage recency values.
Employing this approach, the sequence number associated with a set of mirrored memory locations will keep increasing until it is reset by the inventive mechanism. Although incrementing the sequence numbers, or addition of 1 to each successive sequence number, may be employed to modify the sequence numbers, a variety of different arithmetic operations and algorithms may be employed to modify the sequence numbers for successive write operations and all such variations are included in the scope of the present invention. Such alternative operations include, but are not limited to, subtraction, multiplication, division, boolean operations, and appending alphanumeric characters to sequence numbers.
In a preferred embodiment, during a read operation, the inventive mechanism preferably reads the sequence numbers stored in each of the mirrored memory locations associated with the data being sought, and reads the data associated with the most recent of the sequence numbers read from the various memory locations. The data associated with the most recent of the sequence numbers is then preferably returned as the result of the read operation. Preferably, the inventive mechanism includes an algorithm for recognizing relative recency among the data storage recency values, of which sequence numbers are one variation, which corresponds appropriately to an algorithm used to generate the data storage recency value in the first place. For example, where the algorithm for indicating a higher degree of recency includes incrementing sequence numbers by one when overwriting an existing entry in a memory location, the algorithm for recognizing relative data storage recency among several sequence numbers preferably correlates higher numerical sequence number values with greater degrees of recency. It will be appreciated that other algorithms for recognizing data storage recency values established according to algorithms other than the sequence numbering system discussed above will similarly match the criteria for recognizing data recency with the mechanism intended to indicate data recency when the data storage recency values are first generated.
Accordingly, it is an advantage of a preferred embodiment of the present invention that the recency of data stored in two or more mirrored memory locations may be compared and the most recently stored data read from an appropriately selected one of the mirrored memory locations.
It is a further advantage of a preferred embodiment of the present invention that sequence numbers at various mirrored sites may be reset in order to begin subsequent rounds of sequence number modifications employing a more convenient number.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention.